The present invention is related to a network technology, and more particularly to an ad-hoc wireless network technology, such as Bluetooth, for communicating with public and private local area networks (LANs).
Recently, a radio interface referred to as Bluetooth was introduced to provide wireless, ad hoc networking between mobile phones, laptop computers, headsets, PDAs, and other electronic devices. Some of the implementation details of Bluetooth are disclosed in this application, while a detailed description of the Bluetooth system can be found in “BLUETOOTH—The universal radio interface for ad hoc, wireless connectivity,” by J. C. Haartsen, Ericsson Review No. 3, 1998. Further information about the Bluetooth interface is available on the Official Bluetooth Website on the World Wide Web at http://www.bluetooth.org.
Bluetooth was initially developed to eliminate cables between phones, PC-cards, wireless headsets, etc., but has evolved into an ad-hoc wireless network technology intended for both synchronous traffic, such as voice based traffic, and asynchronous traffic, such as IP based data traffic. Bluetooth promises to provide the ability for any commodity device, such as telephones, PDAs, laptop computers, digital cameras, video monitors, printers, fax machines, to be able to communicate via a radio interface. The commodity devices must contain a Bluetooth radio chip and associated software.
Bluetooth is a wireless communication technology operating in the unlicensed 2.4 GHz ISM (Industrial, Scientific, and Medical) band using a fast frequency-hopping scheme to minimize interference with non-Bluetooth sources. The frequency-hopping occurs nominally at 1,600 hops per second. The system has 79 possible channels, with a typical channel spacing of 1 MHz. Two or more Bluetooth (BT) units sharing the same channel form a piconet, as illustrated in FIG. 1. Each BT unit in a piconet may perform the functions of either a master or slave. Within each piconet there is always exactly one master and up to seven active slaves. Any BT unit can perform the functions of a master in a piconet.
Furthermore, two or more piconets can be wirelessly interconnected to form a scatternet, as illustrated in FIG. 2. The connection point between the two piconets consists of a BT unit that is a member of both piconets. A BT unit can simultaneously be a slave member of multiple piconets. However, a BT unit may only be a master in one piconet at a time, but may simultaneously participate as a slave in other piconets. A BT unit may only transmit and receive data in one piconet at a time, so participation in multiple piconets is done on a time division multiplex basis.
The Bluetooth system provides full-duplex transmission built on slotted Time Division Duplex (TDD), where each slot is 0.625 ms long. The time slots are cyclically numbered sequentially using a large cycle of 227. Master-to-slave transmission always starts in an even-numbered time slot, while slave-to-master transmission always starts in an odd-numbered time slot. An even-numbered master-to-slave time slot and its subsequent odd-numbered slave-to-master time slot together comprise a frame, except when multi-slot packets are used. There is no direct transmission between slaves in a Bluetooth piconet, only between master and slave and vice versa.
Communication within a piconet is organized so that the master polls each slave according to a polling scheme. A slave typically transmits after being polled by the master, with minor exceptions described below. The slave starts its transmission in the slave-to-master time slot immediately following the packet received from the master. The master may or may not include data in the packet used to poll a slave. The only exception to the above principle is that when a slave has an established Synchronous Connection Oriented (SCO) link, which is described further below, the slave may continue to transmit in the pre-allocated slave-to-master time slot, even if not explicitly polled by the master in the preceding master-to-slave time slot.
A globally unique 48 bit IEEE 802 address, called the Bluetooth Device Address (BD_ADDR), is assigned to each BT unit at the time of manufacture, and it is never changed. In addition, the master BT of a piconet assigns a local Active Member Address (AM_ADDR) to each active member of the piconet. The AM_ADDR, which is only three bits long and is assigned and cleared dynamically, is unique only within a single piconet. The master uses the AM_ADDR when polling a slave in a piconet. However, when the slave transmits a packet to the master, in response to a packet received from the master, the slave includes its own AM_ADDR in the packet header, not the master's.
All data is transmitted in packets, which can carry both synchronous data, on SCO links such as voice traffic, and asynchronous data, on Asynchronous Connectionless (ACL) links. An acknowledgment and retransmission scheme is used for ACL link packets to ensure reliable transfer of data. Forward error correction (FEC) may also be employed in the form of channel coding.
The standard format of a Bluetooth packet is illustrated in FIG. 3, although certain control packets may use a different format. The AM_ADDR is located in the packet header followed by some control parameters, for example, a bit indicating an acknowledgment or a re-transmission request of the previous packet, when applicable, and a header error check (HEC).
The format of the payload depends on the type of packet. The payload of a typical ACL packet consists of a header, a data field and a cyclic redundancy check (CRC), except AUX1 type packets. The payload of an SCO packet consists of only a data field. In addition there are hybrid packets including two data fields, one for synchronous data and one for asynchronous data. Packets in which the payload does not include a CRC are neither acknowledged nor re-transmitted.
The protocol layers of a Bluetooth system are illustrated in FIG. 4. The Baseband, LMP and L2CAP are existing Bluetooth specific protocols. The “high level protocol or application” layer represents protocols that may or may not be Bluetooth specific, while the Network layer does not exist in the current Bluetooth specifications (version 1.1).
Since transmission in a piconet is exclusively between the master and a slave, and vice versa with the slave always using its own AM_ADDR, there is no way for a slave to send data to another slave within a piconet. There are no provisions for a slave to address another slave in a direct communication. Hence, a slave can only communicate with the master of the piconet, while the master can communicate with all the slaves.
Another limitation of the Bluetooth system is that in the current standard specifications there is no way to address and route packets from one piconet to another. Inter-piconet communication in a scatternet is not specified.
An important aspect of Bluetooth ad-hoc networking is IP (Internet Protocol) support in a Bluetooth scatternet or piconet, that is, how to run IP on top of the Bluetooth protocol stack. There are currently two basic proposals for providing IP support. The first proposal is to regard each Bluetooth piconet as an IP subnet and let IP route packets between nodes in different piconets. The second proposal is to regard an entire Bluetooth scatternet as an IP subnet. A Network Adaptation Layer (NAL) is inserted between the L2CAP and IP layers, as illustrated in FIG. 5. The NAL emulates a shared medium network, for example, a broadcast medium, which is assumed by the IP layer.
The first proposal suffers from a number of problems, partly because the Bluetooth piconets are not shared medium networks. The second proposal is also problematic, but is more promising. The present invention applies the NAL approach of the second proposal. It is assumed that NAL is an extension of Bluetooth Network Encapsulation Protocol, which is currently a specification work in progress in the Personal Area Networking (PAN) working group in the Bluetooth SIG. Therefore, the Bluetooth scatternet is effectively a bridged Ethernet network, as seen from higher protocol layers, such as IP.
The NAL layer must support a number of features, including a routing mechanism to route packets within a scatternet (there are several ad-hoc routing protocols proposed for this purpose), while emulating a single shared medium network to the IP layer. Regardless of the routing scheme used to route packets through a scatternet, BT units that are members in more than one piconet must forward packets from one piconet to another. These BT units may be referred to as forwarding nodes.
A number of mechanisms in an IP network, for example the ARP (Address Resolution Protocol) and DHCP (Dynamic Host Configuration Protocol) mechanisms, rely on a broadcast mechanism on the underlying link layer, which is usually a shared medium network. Therefore, support for broadcast messages in a Bluetooth scatternet is an important feature of the NAL layer.
The NAL layer can include functions for automatic network formation, which allows nodes to discover neighboring nodes automatically and connect to each other for the purpose of establishing a basic connectivity to facilitate higher-level service discovery. Applications may then use the network for application protocol interactions, according to user interactions or predetermined preferences/criteria.
An automatic network formation scheme may also include nodes discovering and connecting to access points providing access to non-ad-hoc networks, for example fixed wired networks, such as a LAN. FIG. 6 illustrates a possible network topology, where some Bluetooth nodes provide connectivity to the wired network via Bluetooth Access Points AP1 and AP2.
Assuming the wired network is configured with an Ethernet technology, the access points can provide bridging between Bluetooth nodes and the nodes of the wired network. This is possible because the Ethernet packet format can be encapsulated on the Bluetooth side, and the Bluetooth BD_ADDRs are assigned in the same address range as, for example, Ethernet/Token Ring/Token Bus network cards.
When bridging is performed, it is important to limit unnecessary broadcast propagation in the network, and it is imperative to prevent broadcast loops. Limiting broadcast propagation through access points can be accomplished by performing filtering within the access points. However, preventing broadcast loops is particularly problematic when a Bluetooth scatternet is connected at two or more places to a wired network via Bluetooth access points. Another possible implementation to consider is a situation where a Bluetooth scatternet is connected at two or more BTs to access points in different wired networks, which may be owned and operated by different organizations.
Scalability and security in automatic network formation are other issues that must be addressed. Ideally, nodes need the ability to join in a “public” scatternet, for applications such as anonymous gaming, as well as “private” scatternets for more sensitive applications. A question arises regarding how to restrain nodes from inappropriately forming interconnections between a public and private scatternet.
The work performed by the MANET working group within the IETF (Internet Engineering Task Force) is representative of the state-of-the-art in the ad-hoc routing area. A mobile ad-hoc network (MANET) is an autonomous system of mobile routers, and their associated hosts, connected by wireless links. The mobile routers are free to move randomly and organize themselves arbitrarily. Thus, the network's wireless topology changes rapidly and unpredictably. A MANET may operate in a standalone fashion, or may be connected to the Internet.
Applying MANET protocols at the Bluetooth NAL layer may solve the problem with broadcast loops within the scatternet, but does not address the problem of broadcast loops with scatternets bridged to a LAN, or of bridging LANs together.
The IEEE develops standards for LANs employing, for example, Ethernet and Wireless LAN network technologies. The IEEE 802.1D [5] standard describes the operation of Ethernet bridges, and defines a spanning tree algorithm and protocol that is executed by bridging devices to avoid the broadcast loop problem in bridged Ethernet networks. However, there is no proposed solution for the problems caused by unintentional erroneous interconnection of organizationally separated networks through Bluetooth scatternets.
The IEEE 802.11 wireless LAN technology does have a mechanism to assign a “network identity” to access points that belong to the same network. This network identity is also configured into all client devices using the network to prevent their erroneous connection to a neighboring company's network in cases of radio coverage overlap. However, while in ad-hoc mode, all IEEE 802.11 LAN cards synchronize to the same channel.
Yet another relevant technology is Virtual LANs (VLAN). VLANs are described in IEEE 802.1Q [7], which introduces a possibility for tagging of Ethernet frames with their VLAN identity.
The protocols mentioned above, while relevant, are not particularly efficient in the context of Bluetooth. Even when applied together in every conceivable combination, they fail to address all the aforementioned problems, such as the formation of broadcast loops when scatternets are bridged to LANs at multiple BTs, the prevention of inappropriately interconnected LANs, and scoped scatternets (public/private). For example, requiring all Bluetooth nodes to be able to perform the IEEE 802.1D functions would solve the scatternet problem and the problem with broadcast loops when scatternets are bridged to LANs at multiple BTs. However, this solution would not prevent inappropriate interconnection between LANs that should remain separated. It is also widely believed in the PAN working group, but not universally accepted, that the use of a spanning tree is inappropriate, since the spanning tree is a proactive approach that doesn't optimize the network topology in any way, but only fixes the broadcast loop problem.
The MANET ad-hoc routing protocols are more appropriate for adaption to Bluetooth, since they are reactive, and thus respond better to changing topologies. However, using an ad-hoc routing protocol in Bluetooth scatternets presents other complications, such as the broadcast loop problem that occurs when scatternets are bridged to LANs at multiple BTs.
Accordingly, there is a need to provide a method of interfacing ad-hoc wireless networks to wire networks that eliminates broadcast loops when scatternets are bridged to LANs at multiple BTs, that prevents the formation of inappropriately interconnected LANs, and that addresses the concerns regarding scoped scatternets (public/private).